1. Field of the Invention
The present invention relates generally to the field of packet data networks, and, more particularly, to the application of inverse multiplexing in packet switching systems.
2. Description of the Related Art
Inverse multiplexing has long been known as a technique to implement a single high-capacity logical communication channel by using several lower-capacity communication channels, where distribution and aggregation of the traffic flow to and from individual communication links is transparent to the applications. A variety of such inverse multiplexing schemes for packet data networks were proposed and implemented such as incremental bandwidth on demand (BONDING), Multilink Point-to-Point protocol (Multilink PPP), Packet Striping and Inverse multiplexing for ATM (IMA), for example. The aforementioned techniques primarily are related to different operating environments, have different objectives, and can be classified in respect to splitting granularity, synchronous vs. asynchronous use of resources, and methods of differential delay compensation. However, aggregation of communication bandwidth through splitting, recombination, and sequencing is a feature that they have in common. Other common features include: operating on the point-to-point link and sensitivity to packet loss. The former means that the underlying lower capacity channels are in fact point-to-point links which do not contain contention points associated with switching nodes and, therefore, can be characterized by predictable delay and low delay variation. Furthermore, the splitting and recombination scheme may rely on the exclusive use of those links for the inverse multiplexing purposes. The latter implies that loss of just a single packet within the boundaries of the inverse multiplexed logical channel may cause loss of synchronization and lead to the necessity for some number of successfully delivered packets to be discarded as well. Discarding of the successfully delivered packets, in turn, is associated with the need to retransmit the packets later, causes reduction of throughput, and is a contributing factor of network congestion.
In recent years, it has become obvious that point-to-point inverse multiplexing does not address all the needs of modern packet data networks. While the market demands switches that are capable of terminating trunks of ever increasing bandwidth, the issue of scaling the port capacity becomes critical. Inverse multiplexing can potentially provide an economical way to interface the new higher-rate trunks with existing switches (or switching networks) that have ports operating at a lower rate.
However, the principles of inverse multiplexing applicable in the point-to-point environment can not be directly translated into the switching systems. First, in this case, splitting has to distinguish between multiple components of the incoming packet flow which are destined to distinct output ports of the switching system and carry different Quality of Service (QoS) requirements. Second, the presence of buffers within the boundaries of the logical link make the differential delays unpredictable and highly variable, as well as is associated with inherent probability of packet loss.
An improved inverse multiplexing scheme called switched connection inverse multiplexing, which presents a significant qualitative advancement over conventional point-to-point inverse multiplexing, has been proposed recently. This new switched connection inverse multiplexing scheme applies to any packet data network, operates on individual established network connections or flows, and allows inverse multiplexed packets of the selected network connections over network segments which contain switching nodes. The scheme is generally directed to a packet switching system including a plurality of input controllers and a plurality of output controllers attached to a core switching network. Each input controller and each output controller terminates a communication link that can carry a plurality of network connections (NCs). Each NC is received at a unique input controller and is routed through the core switching network to a unique output controller. The core switching network provides a plurality of switching paths between each input controller and each output controller such that the bandwidth of each individual switching path is smaller than the data rate of the communication links terminated by a controller, but the aggregate bandwidth of all the switching paths provided between a given pair of input and output controllers is approximately equal to the data rate of the terminated communication links.
The packet switching system processes NC requests for switched connections between the incoming communication links and the outgoing communication links. Non-multiplexed NCs are established through the core switching network in which the entire bandwidth of the NC is carried by a single switching path. Inverse multiplexed NCs are established through the core switching network in which the bandwidth of the NC is partitioned among a plurality of switching paths using weight values to determine the fraction of bandwidth to be allocated to each switching path, each portion of the NC traffic taking a separate switching path being referred to as a subconnection.
Every packet of an inverse multiplexed NC is assigned an inverse multiplexing tag, which contains a sequence number consistent within the subconnection, i.e., it reflects the number of packets belonging to every given inverse multiplexed NC transmitted over the same switching path, and a next path pointer, i.e., the identification of the switching path on which the following packet of the same inverse multiplexed NC will be transmitted. To enhance robustness of the scheme, the inverse multiplexing tag may optionally contain one or more i-th previous next path pointers, i=1, . . . , n, the i-th previous next path pointer meaning the value of the next path pointer that has been carried by the i-th preceding packet belonging to the same subconnection.
The switched connection inverse multiplexing scheme successfully translates the resource aggregation principles from point-to-point link bandwidths to switch port capacities in a switching system. However, the issue of confronting packet loss remains critical. To eliminate preventable packet losses within the inverse multiplexed switching path and to transfer them to the input controller before the actual splitting point, the switched connection inverse multiplexing scheme employs ubiquitous back pressure applied through all stages of the core switching network from the output controller to the input controller. Still not all types of packet losses can be excluded by this method. If the back pressure to the input controller can not be applied or is ineffective at the specific location within the core switching network where loss can occur, or if packet losses are associated with random uncontrollable factors, such as the electrical glitches, packet memory faults, or interface errors, the packet re-sequencing engine may lose synchronization and be unable to restore the original order of the inverse multiplexed NC packets. In particular, if the number of packets from the same subconnection of the given inverse multiplexed NC which have been lost in a row exceeds n, i.e., the number of previous next path pointers contained in the inverse multiplexing tag, then restoring the packet order of the given inverse multiplexed NC becomes impossible.
Therefore, there is a need for improved methods and devices which address these and other shortcomings of the prior art.
The present invention generally is directed to a packet switching system which provides a fault tolerant extension of the switched connection inverse multiplexing scheme. In a preferred embodiment, the packet switching system incorporates a core switching network including a plurality of input and output ports and a plurality of switching paths between the input and output ports. Preferably, a plurality of input controllers and output controllers are provided, with each of the input controllers being attached to a plurality of the input ports and each of the output controllers being attached to a plurality of the output ports. Additionally, the core switching network is configured to receive a first flow of data packets from one of the input controllers and deliver a second flow of data packets to one of the output controllers, and the packet switching system is configured to restore the second flow of data packets despite a loss of information from at least one of the data packets upstream of the one of the output controllers so that the second flow has an order of remaining ones of the data packets corresponding to an order of the data packets in the first flow.
In accordance with another aspect of the present invention, a preferred embodiment of the packet switching system incorporates a core switching network including a plurality of input ports, a plurality of output ports, and a plurality of switching paths between the ports. Preferably, a plurality of input controllers are provided, with each of the input controllers being configured to receive a first flow of data packets, to partition the first flow of data packets into at least two sequences of data packets, and forward each of the sequences of data packets to a different one of the input ports. Additionally, a plurality of output controllers are provided, with each of the output controllers being configured to receive at least two sequences of remaining ones of the data packets from different ones of the output ports and to re-assemble the sequences of remaining ones of the data packets into a second flow of data packets. Preferably, the second flow has an order of the remaining data packets corresponding to an order of the data packets in the first flow despite a possible loss of at least one of the data packets within the core switching network.
In accordance with another aspect of the present invention, a core switching network is provided. In a preferred embodiment, the core switching network incorporates a plurality of input ports, a plurality of output ports, and a plurality of switching paths between the input and output ports. Means for delivering the data packets through the core switching network also is provided.
In accordance with still another aspect of the present invention, a method for resorting a flow of data packets in a packet switching system is provided. A preferred method incorporates the steps of assigning an inverse multiplexing tag to each of the data packets, saving the inverse multiplexing tag of each of the data packets discarded by the packet switching system, and resorting successfully delivered ones of the data packets based upon the inverse multiplexing tags of the successfully delivered ones of the data packets and the saved inverse multiplexing tags of the discarded data packets.
In accordance with yet another aspect of the present invention, a method for restoring a flow of data packets in a packet switching system is provided. A preferred method incorporates the steps of providing a first flow of data packets to a core switching network of the packet switching system, inserting a checkpoint into the first flow of data packets, providing a second flow of data packets from the core switching network, and utilizing the checkpoint to recover from a loss of information from within the core switching network so that the second flow has an order of remaining ones of the data packets corresponding to an order of the data packets in the first flow.